1、翻转单词顺序
思想：利用双指针，将i定义为最后一个一个字符位置，让j指向，然后i前移，找到空格，那么i-j之间的就是一个单词，利用之此方法，可以将每个单词倒着放到s中
但是得 注意去多余的空格，各个单词之间的以及头尾
class Solution {
public:
    string reverseWords(string s) {
        if(s.empty())
            return s;
        string s1;
        int i=s.size()-1;
        int j=0;
        while(i>=0)
        {
            //除空格
            while(i>=0&&s[i]==' ')
                i--;
            j=i;//j为不是空格单词得尾部
            //找空格
            while(i>=0&&s[i]!=' ')
                i--;
            int cur=i+1;
            for(int i=cur;i<=j;i++)
            {
                s1.push_back(s[i]);
            }
            while(i>=0&&s[i]==' ')
                i--;
            if(i>=0)
                s1.push_back(' ');
        }
        
        return s1;
    }
};

2、背包问题
思想：动态规划
f(i,j)表示前i个物品背包重量为j时的最大价值
f(i,j)可以由max(f(i-1,j),f(i-1,j-m[i]+v[i-1]))解释就是如果加了第i个物品那么得留第i个物品的重量。
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 计算01背包问题的结果
     * @param V int整型 背包的体积
     * @param n int整型 物品的个数
     * @param vw int整型vector<vector<>> 第一维度为n,第二维度为2的二维数组,vw[i][0],vw[i][1]分别描述i+1个物品的vi,wi
     * @return int整型
     */
    int knapsack(int V, int n, vector<vector<int> >& vw) {
        // write code here
        vector<vector<int>> v(n+1,vector<int>(V+1,0));//表示从i个物品中，体积为j时的最大物品
       
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=V;j++)
            {
                if(vw[i-1][0]<=j)
                {
                    v[i][j]=v[i-1][j]>(v[i-1][j-vw[i-1][0]]+vw[i-1][1])?v[i-1][j]:(v[i-1][j-vw[i-1][0]]+vw[i-1][1]);
                }
                else
                    v[i][j]=v[i-1][j];
            }
        }
        return v[n][V];
    }
};